COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "let.pub[let,jmc]" source
C00011 ENDMK
C⊗;
.require "let.pub[let,jmc]" source;
.FONT d "SUB";
.FONT e "GRKB30";
.TURN ON "_" FOR "#"
.at "q1" ⊂"%d1%*"⊃
.at "q2" ⊂"%d2%*"⊃
.at "qi" ⊂"%di%*"⊃
.at "qn" ⊂"%dn%*"⊃
.at "qf" ⊂"%ef%*"⊃
∂CSL Dr. Stephen Wolfram↓Institute for Advanced Study↓Princeton, NJ 08540∞

Dear Steve:

	Thanks for your %2Cellular Automata: towards a paradigm for
complexity%1.  I found it quite clear and some of the results curious.
However, it did not relieve my previous doubts about that line of research.

	Getting appropriate paradigms for complexity is of great importance.
It seems doubtful to me that complexity of intellect, biological complexity
and the complexities associated with physical phenomena like turbulence
will all belong to similar paradigms.

	Also I have considerable doubt whether cellular automata in
general relate well to any of these, although they are most likely
to relate to turbulence-type complexity.  The fact that they are not
selected for, either naturally or by thinking, is the main reason.
In any case I have the following remarks.

	1. Any finite collection %B(Aq1, ... ,Aqn)%1 of cellular automata
can be superposed into a single automaton %BA%1 with %Br_=_max(rq1,_..._,rqn)%1
and %Bk_=_kq1kq2...kqn%1.  The state space of %BA%1 is just an
enumeration of the Cartesian product of the state spaces of
%BAq1,_..._,Aqn%1, and the qf just involves the product of the qfqi's
acting independently.  A suitable notation is an exercise for anyone
who finds the concept promising.  Therefore, behaviors corresponding
to the superposition of behaviors of separate automata are readily
produced.

	2. Any Turing machine is trivially a cellular automaton.  The
state space of the cellular automaton is the product of three spaces -
the state space of the Turing machine, the symbol space of the Turing
machine, and one bit quantity called the %Bactivity%1.  Corresponding
to a state of the Turing machine is any state of the cellular
automaton in which exactly one cell has %Bactivity_=_1%1.  The
law of motion of the automaton specifies that any cell of the
automaton such that it and its neighbors have %Bactivity_=_0%1 retains
its state.  The active cell and its neighbors change state in a way
that is in obvious correspondence to the table of the Turing machine.
This also settles your conjecture about universality.

	3. All the known possible behaviors of Turing machines therefore
carry over into possible behaviors of cellular automata, and this
shows that your experimentally suggested classification of the behaviors
of cellular automata is far from exhaustive.  Although statistical
experiments might suggest that the most cellular automata fit your
classification, any kind of natural or artificial selection might
concentrate on those that don't.

	4. This suggests the invention of cellular automata exhibiting
interesting behavior as a supplement to statistical experiment.

	5. Here is an example of a realizable exotic behavior.
Your favorite cellular automaton, a Turing machine to be described
subsequently, and a third component are approximately superposed.
The Turing machine looks for a counter-example to Fermat's last
theorem. However, it does so while moving to the right after each
trial tuplet %B(x,y,z,n)%1 so that any finite region of the tape
becomes inactive in that component as long as no counter-example
has been found.  The third component remains passive until the
Turing machine activates it on finding the counter-example.  Then
it does whatever you please.  For example, it may wipe out the first
component, i.e. make its state 0, and then begin some arbitrary behavior.

	6. The point of this exotic example and others you might
construct is that cellular automata are too general to give insight
into complexity unless additional assumptions are made.  If you
want physics, you must put in some physical assumptions.  If you
want biology you must put that in, and if you want computers or
intellectual life you must design them or make a "biological" system
and wait a very long time for them to evolve.

	7. One might hope to learn something by studying cellular
automata with small %Bk%1 and %Br%1.  However, experience with
similar (1950s and 1960s) studies of Turing machines with small
numbers of states and symbols suggest that this hope is rather
forlorn.  The search for universal Turing machines with minimal
state-symbol product degenerated into inventing ever more complicated
coding schemes to prove their universality.  I believe that simulation experiments
also didn't lead to much.

	8. The number of feedback systems leading to chaotic behavior
is legion.  You can point a camera at the screen or iterate copying
a pattern on a xerox machine or repeatedly copy a tape loop onto
itself.  In each case you can put some device in for transforming
the signal in series with the copying.  Most adjustments of the
system lead to degenerate fixed points, but experiment can find
patterns with considerable structure.  Display hack programs are in the
same general class.

	9. Of course the mathematical formalisms for quantifying
the disorder are new and so is the topological classification of
some of the cases.  Nevertheless, I still doubt that applying
these formalisms to cellular automata will by itself tell much
about physics, biology or computation.

	10. Cellular automaton models embodying some specific
features of the domain under study may be more fruitful.

.sgn